%\newcommand{\prb}[2]{p_{#1,#2}}
\section{Proofs for the two-hop walk in directed graphs}
\label{app:directed}
\begin{LabeledProof}{Theorem~\ref{thm:directed.upper-10p}}
Consider any pair of nodes, $u$ and $v$.  Consider a shortest path
from $u$ to $v$ $\rb{v_0,v_1,v_2,\dots,v_m}$, where $v_0 = u$, $v_m =
v$ and $m \le n$.  Fix a time step $t$.  Let $e_i$ denote the event an
edge is added from $v_i$ to $v_{i+2}$ in step $t$. The probability of
occurrence of $e_i$ is $\prob{e_i}\ge 1/n^2$. All the $e_i$'s are
independent from one another.
\begin{eqnarray*}
\prob{\cup_i e_i} &\ge& \sum_i \prob{e_i} - \sum_i \sum_j \prob{e_i\cap e_j} \\
 &=& \sum_i \prob{e_i} - \sum_i \sum_j \prob{e_i} \prob{e_j} \\
 &\ge& m\frac{1}{n^2} - m(m-1) \frac{1}{n^4} \\
 &\ge& \frac{m}{n^2}
\end{eqnarray*}
Let $X_1$ denote the number of steps it takes for the length of the
above path to decrease by $1$.  It is clear that $E[X_1] \le n^2/m$.
In general, let $X_i$ denote the number of steps it takes for the
length of the above path to decrease by $i$.  By
Lemma~\ref{lem:couponcorollary-10p}, the number of steps it takes for
the above path to shrink to an edge is at most $4 n^2 \ln n$ with
probability $1/n^3$.  Taking a union bound over all the edges yields
the desired upper bound.

For the lower bound, consider a graph $\gf{0}$ with the node set
$\{1, 2, \ldots, n\}$ and the edge set 
\[
\{(3i,j), (3i+1,j): 0 \le i < n/4, 3n/4 \le j < n \} \bigcup \{(3i,
3i+1), (3i+1, 3i+2): 0 \le i < n/4\}.
\] 
The only edges that need to be added by the two-hop process are the
edges $(3i,3i+2)$ for $0 \le i < n/4$.  The probability that node
$3i$ adds the edge $(3i,3i+2)$ in any round is at most $16/n^2$.  The
probability that edge $(3i,3i+2)$ is not added in $(n^2 \ln n)/32$
rounds is at least $1/\sqrt{n}$.  Since the events associated with
adding each of these edges are independent, the probability that all
the $n/3$ edges are added in $(n^2 \ln n)/32$ rounds is at most $(1 -
1/\sqrt{n})^{n/3} \le e^{-\sqrt{n}/3}$, completing the lower bound
proof.
\end{LabeledProof}

\smallskip

\begin{LabeledProof}{Theorem~\ref{thm:directed.lower-10p}}
The graph $\gf{0}=(V,E)$ is depicted in Figure~\ref{fig:digraph+lower}
and formally defined as $\gf{0} = (V,E)$ where $V=\cub{1,2,\dots,n}$
with $n$ being even, and
\[
E = \cub{\rb{i,j}: 1 \le i,j \le n/2} \cup \cub{\rb{i,i+1} : n/2 \le i <
  n} \cup \cub{\rb{i,j}: i > j, i > n/2, i,j\in V}.
\]
\begin{figure}[ht]
\begin{center}
  \includegraphics[width=5in]{./figures/diexample.jpg}
  \caption{Lower bound example for two-hop walk process in directed graphs}
  \label{fig:digraph+lower}
\end{center}
\end{figure}
We first establish an upper bound on the probability that edge
$(i,i+h)$ is added by the start of round $t$, for given $i$, $1 \le i
\le n -h$.  Let $\prb{h}{t}$ denote this probability.  The following
base cases are immediate: $\prb{h}{0}$ is $1$ for $h = 1$ and $h < 0$,
and $0$ otherwise.  Next, the edge $(i,i+h)$ is in $\gf{t+1}$ if and
only if $(i,i+h)$ is either in $\gf{t-1}$ or added in round $t$.  In
the latter case, $(i,i+h)$ is added by a two-hop walk $i \rightarrow i
+ k \rightarrow i + h$, where $-i < k \le n - i$.  Since the
out-degree of every node is at least $n/2$, for any $k$ the
probability that $i$ takes such a walk is at most $4/n^2$.
\begin{eqnarray}
\prb{h}{t+1} & \le & \prb{h}{t} + \frac{4}{n^2} \sum_{k > -i}^{n-i} \prb{k}{t}\prb{h-k}{t} \nonumber\\
& = & \prb{h}{t} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \prb{h+k}{t} + \sum_{k=1}^{h-1} \prb{k}{t}\prb{h-k}{t} + \sum_{k=h+1}^{n-i} \prb{k}{t}\right) \label{eqn:lower}
\end{eqnarray}
We show by induction on $t$ that 
\begin{eqnarray}
\prb{h}{t} \le \left(\frac{\alpha t}{n^2}\right)^{h-1}, \mbox{ for all } t \le \eps n^2  \label{eqn:prb}
\end{eqnarray}
where $\alpha$ and $\eps$ are positive constants that are specified
later.

The induction base is immediate.  For the induction step, we use the
induction hypothesis for $t$ and Equation~\ref{eqn:lower} and bound
$\prb{h}{t+1}$ as follows.
\begin{eqnarray*}
\prb{h}{t+1} & \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left(\sum_{k = 1}^{i-1} \left(\frac{\alpha t}{n^2}\right)^{h+k-1} + \sum_{k=1}^{h-1} \left(\frac{\alpha t}{n^2}\right)^{k-1} \left(\frac{\alpha t}{n^2}\right)^{h-k-1} + \sum_{k=h+1}^{n-i} \left(\frac{\alpha t}{n^2}\right)^{k-1}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + \frac{4}{n^2} \left( (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2} + \left(\frac{\alpha t}{n^2}\right)^{h} \frac{2}{1 - \alpha t/n^2}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1)\left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{1}{n^2} \left(4 + \frac{4\eps^2}{(1 - \alpha\eps)}\right)\\
& \le & \left(\frac{\alpha t}{n^2}\right)^{h-1} + (h-1) \left(\frac{\alpha t}{n^2}\right)^{h-2}\frac{\alpha}{n^2}\\
& \le & \left(\frac{\alpha (t+1)}{n^2}\right)^{h-1}.
\end{eqnarray*}
(In the second inequality, we combine the first and third summations
and bound them by their infinite sums.  In the third inequality, we
use $t \le \eps n^2$.  For the fourth inequality, we set $\alpha$
sufficiently large so that $\alpha \ge 4 + 4/(1-\alpha \eps)$.  The
final inequality follows from Taylor series expansion.)

For an integer $x$, let $C_x$ denote the cut $(\{u: u \le x\}, \{v, v
> x\})$.  We say that a cut $C_x$ is {\em untouched}\/ at the start of
round $t$ if the only edge in $\gf{t}$ crossing the cut $C_x$ is the
edge $(x, x+1)$; otherwise, we say $C_x$ is {\em touched}.  Let $X$
denote the smallest integer such that $C_X$ is untouched.  We note
that $X$ is a random variable that also varies with time.  Initially,
$X = n/2$.

We divide the analysis into several phases, numbered from $0$.  A
phase ends when $X$ changes.  Let $X_i$ denote the value of $X$ at the
start of phase $i$; thus $X_0 = n/2$.  Let $T_i$ denote the number of
rounds in phase $i$.  A new edge is added to the cut $C_{X_i}$ only if
either $X_i$ selects edge $(X_i,X_i+1)$ as its first hop or a node
$u < X_i$ selects $u \rightarrow X_i \rightarrow X_i + 1$.  Since the
degree of every node is at least $n/2$, the probability that a new
edge is added to the cut $C_i$ is at most $2/n + n(4/n^2) = 6/n$,
implying that $E[T_i] \ge n/6$.

We now place a bound on $X_{i+1}$.  Fix a round $t \le \eps n^2$, and
let $E_x$ denote the event that $C_x$ is touched by round $t$.  We
first place an upper bound on the probability of $E_x$ for arbitrary
$x$ using Equation~\ref{eqn:prb}.
\[
\Pr[E_x] \le \sum_{h \ge 2} h \left(\frac{\alpha t}{n^2} \right)^{h-1} \le \frac{\alpha t (4 - 3(\alpha t)/n^2 + (\alpha t)^2/n^4)}{n^2(1-(\alpha t)/n^2)^3},
\]
for $t \le \eps n^2$, where we use the inequality $\sum_{h \ge 2} h^2
\delta^h = \delta(4-3\delta+\delta^2)/(1-\delta)^3$ for $0 < \delta <
1$.  We set $\eps$ sufficiently small so that
$(4-3\eps+\eps^2)/(1-\eps)^3 \le 5$, implying that the above
probability is at most $5\eps$.

If $E_x$ were independent from $E_y$ for $x \neq y$, then we can
invoke a straightforward analysis using a geometric probability
distribution to argue that $E[X_{i+1} - X_i]$ is at most $1/(1-5\eps)
= O(1)$; to see this, observe that $X_{i+1} - X_i$ is stochastically
dominated by the number of tosses of a biased coin needed to get one
head, where the probability of tail is $5\eps$.  The preceding
independence does not hold, however; in fact, for $y > x$, $\Pr[E_y
  \mod E_x] > \Pr[E_y]$.  We show that the impact of this correlation
is very small when $x$ and $y$ are sufficiently far apart.  We
consider a sequence of cuts $C_{x_1}, C_{x_2}, \ldots, C_{x_\ell},
\ldots$ where $x_\ell = x_{\ell-1} + c\ell$, for a constant $c$ chosen
sufficiently large, and we set $x_0 = X_i + 2$.  We bound the
conditional probability of $E_{x_\ell}$ given $E_{x_{\ell -1}} \cap
E_{x_{\ell-2}} \cdots \cap E_{x_1}$ as follows.
\begin{eqnarray*}
& & \Pr[E_{x_\ell} | E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]\\
& = & \frac{\Pr[E_{x_\ell} \cap E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1} \cap (C_{x_\ell} \cap (C_{x_{\ell-1}} \cup \cdots \cup C_{x_1}) = \emptyset)]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]} +\\
& & 
\frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1} \cap (C_{x_\ell} \cap (C_{x_{\ell-1}} \cup \cdots \cup C_{x_1}) \neq \emptyset)}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \frac{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}] \Pr[\mbox{a new edge is added from } (x_{\ell-1} +1, x_\ell) \mbox{ to } (x_\ell+1,n]]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& & \frac{\Pr[\mbox{an edge spanning at least } c\ell \mbox{ hops is added across } C_{x_\ell}]}{\Pr[E_{x_{\ell -1}} \cap E_{x_{\ell-2}} \cdots E_{x_1}]}\\
& \le & \Pr[E_{x_\ell}] + \frac{((\alpha t)/n^2)^{c\ell-1}}{(1 - \alpha t/n^2)^2(t/n^2)^{\ell}}\\
& \le & 5\eps + \eps = 6\eps,
\end{eqnarray*}
where we set $c$ sufficiently large in the last step.  Since $X_{i+1}$
is at most the smallest $x_\ell$ such that $C_{x_\ell}$ is untouched, 
we obtain that
\begin{eqnarray*}
E[X_{i+1} - X_i] \le 2 + \sum_{\ell \ge 2} (6 \eps)^\ell c\ell^2 \le c',
\end{eqnarray*}
for a constant $c'$ chosen sufficiently large.  We thus obtain that
after $\eps' n$ phases, $E[X]$ is at most $\eps'c' n$, where $\eps'$
is chosen sufficiently small so that $n - E[X]$ is $\Omega(n)$.  Since
the expected length of each phase is at least $n/6$, it follows that
the expected number of rounds it takes for the two-hop process to
complete is $\Omega(n^2)$ rounds.  \junk{Let $e_i$ be the event of
  adding an edge from node $i$ to node $i+2$. $\prob{e_i}\le 4/n^2$
  $\forall i\ge n/2$. And all $e_i$'s are independent. We will show it
  takes $\Omega(n^{2})$ time for all $e_i$'s ($i\ge n/2$) to
  happen. Let $r_i$ be the event of adding an edge from node $i$ to
  node $i+3$. $\forall i$, the probability that $r_i$ happens in
  $n^{2}/4$ rounds is
\begin{eqnarray*}
\prob{r_i\mbox{ in }n^{2}/4\mbox{ rounds}} &=& {n^{2}/4 \choose 2}\prob{e_i}\prob{r_i|e_i} \\
&=& \frac{n^2/4(n^2/4-1)}{2} \frac{4}{n^2} \frac{4}{n^2} \\
&\le& \frac{1}{2}
\end{eqnarray*}
Therefore,
\[\prob{\mbox{more than }\ln n\mbox{ } r_i\mbox{'s happen in }n^2/4\mbox{ rounds}} \le \frac{1}{n}\]
\begin{figure}[ht]
\begin{center}
  \includegraphics[width=3in]{./figures/diexample2.jpg}
  \caption{Bad events of 2-step random walk in directed graph}
  \label{fig:digraph+lower+badevent}
\end{center}
\end{figure}
As shown in Figure \ref{fig:digraph+lower+badevent}, such $r_v$ event
will increase the probability of $e_{v+1}$. Since such bad event won't
be more than $\ln n$ with probability at least $1-1/n$, we can look at
the other $n/2-\ln n$ $e_i$'s. In $n^2/4$ rounds, with constant
probability not all $e_i$'s will complete. Thus, the lower bound for
2-hop random walk process in directed graph is $\Omega(n^2)$.
}

\end{LabeledProof}
